package 纯数组;

public class JZ04二维数组中的查找 {

    /**
     * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
     * 每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，
     * 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     *
     * 示例:
     * 现有矩阵 matrix 如下：
     * [
     *   [1,   4,  7, 11, 15],
     *   [2,   5,  8, 12, 19],
     *   [3,   6,  9, 16, 22],
     *   [10, 13, 14, 17, 24],
     *   [18, 21, 23, 26, 30]
     * ]
     * 给定 target = 5，返回 true。
     * 给定 target = 20，返回 false。
     *
     * 限制：
     * 0 <= n <= 1000
     * 0 <= m <= 1000
     */

    /**
     * 本解非最优解,在速度上可能会慢一点。
     * 最优解:从右上角往左往下看,那就是排序好的数组,并且每次遍历都会几个元素。
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {

        int allLength=matrix.length;
        if(allLength<1){
            return false;
        }
        int itemLength=matrix[0].length;
        //两次二分查找 1.先找横排 2.再找竖排

        //横排
        for (int i = 0; i < allLength; i++) {
            if(matrix[i][0]<=target&&matrix[i][itemLength-1]>=target){

                int left=0;
                int right=itemLength-1;
                int mid;

                while (left<=right){
                    mid=(right-left)/2+left;
                    if(matrix[i][mid]>target){
                        right=mid-1;
                    }else if(matrix[i][mid]<target){
                        left=mid+1;
                    }else{
                        return true;
                    }
                }

            }
        }

        //竖排
        for (int i = 0; i < itemLength; i++) {
            if(matrix[0][i]<=target&&matrix[allLength-1][i]>=target){

                int left=0;
                int right=allLength-1;
                int mid;

                while (left<=right){
                    mid=(right-left)/2+left;
                    if(matrix[mid][i]>target){
                        right=mid-1;
                    }else if(matrix[mid][i]<target){
                        left=mid+1;
                    }else{
                        return true;
                    }
                }

            }
        }

        return false;
    }

    public static void main(String[] args) {
        JZ04二维数组中的查找 jz=new JZ04二维数组中的查找();
        int[][] arr={
                };
        boolean result = jz.findNumberIn2DArray(arr, 5);
        System.out.println(result);
    }

}
